package 深度优先搜索;

import common.TreeNode;

public class Solution337打家劫舍3 {

    /**
     * 深度优先搜索
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        if(root==null){
            return 0;
        }
        return doRob(root);
    }

    private int doRob(TreeNode node){
        if(node==null){
            return 0;
        }
        /*抢当前节点和不抢当前节点求最大值*/
        int include=node.val;
        int exclude=doRob(node.left)+doRob(node.right);
        if(node.left!=null){
            include+=doRob(node.left.left);
            include+=doRob(node.left.right);
        }
        if(node.right!=null){
            include+=doRob(node.right.left);
            include+=doRob(node.right.right);
        }

        return Math.max(include,exclude);

    }

    /**
     * 动态规划 性能更好
     * @param root
     * @return
     */
    public int rob2(TreeNode root) {
        int[] dp = doit(root);
        return Math.max(dp[0], dp[1]);
    }

    private int[] doit(TreeNode root){
        int[] dp = new int[2];
        if(root == null){
            return dp;
        }
        int[] left = doit(root.left);
        int[] right = doit(root.right);

        //dp[0]代表不包含root结点，那么值就是左树➕右数之和
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //dp[1]代表包含root结点，那么值就是去掉它的两个子节点之后的两子树之和
        dp[1] = left[0] + right[0] + root.val;

        return dp;
    }
}
